/*
 * @lc app=leetcode.cn id=1268 lang=typescript
 *
 * [1268] 搜索推荐系统
 */

// @lc code=start

class TireNode {
  isWord: boolean;
  next: Map<string, any>;
  // 保存当前前缀的products
  products: string[];
  constructor() {
    this.isWord = false;
    this.next = new Map();
    this.products = [];
  }
}

class Tire {
  root: TireNode;
  constructor() {
    this.root = new TireNode();
  }

  insert(word: string) {
    let node = this.root;
    for (let char of word) {
      if (!node.next.has(char)) {
        node.next.set(char, new TireNode());
      }
      node = node.next.get(char);
      node.products.push(word);
      node.products.sort();
      // 维持最多3个product
      if (node.products.length > 3) node.products.pop();
    }
    if (node.isWord) return false;
    node.isWord = true;
    return true;
  }

  search(word: string): string[][] {
    let node = this.root;
    const res: string[][] = [];
    for (let char of word) {
      if (node.next.has(char)) {
        node = node.next.get(char);
        res.push(node.products);
      } else {
        // 树中没有后续字符了
        // 方便后面继续生成空数组
        node = new TireNode();
        res.push([]);
      }
    }
    return res;
  }
}

function suggestedProducts(products: string[], searchWord: string): string[][] {
  const tire = new Tire();
  for (let product of products) {
    tire.insert(product);
  }

  return tire.search(searchWord);
}
// @lc code=end
